package 力扣.位运算.异或运算;

import java.util.*;

public class 猜字谜1178 {
    public static void main(String[] args) {
//        String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
//        String[] puzzles = {"aboveyz","abcd","abslute","absoryz","actresz","gaswxyz"};
        String[] words = {"apple","pleas","please"};
        String[] puzzles = {"aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"};
        List<Integer> numOfValidWords = findNumOfValidWords2(words, puzzles);
        System.out.println(numOfValidWords);
    }

    /**
     * 此方法通用，但是超时
     * @param words
     * @param puzzles
     * @return
     */
    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        int[] tewords = new int[words.length];
        int[] tepuzzles = new int[puzzles.length];
//        int[] res = new int[puzzles.length];
        ArrayList<Integer> rets = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                 tewords[i] |= 1 << (word.charAt(j) - 97);
            }
        }
        for (int i = 0; i < puzzles.length; i++) {
            String puzzle = puzzles[i];
            for (int j = 0; j < puzzle.length(); j++) {
                 tepuzzles[i] |= 1 << (puzzle.charAt(j) - 97);
            }
        }
//        System.out.println(Arrays.toString(tewords));
//        System.out.println(Arrays.toString(tepuzzles));
        for (int i = 0; i < puzzles.length; i++) {
            String puzz = puzzles[i];
            char c = puzz.charAt(0);
            int p = c - 97;//第一个单词在哪一位 (此位必为1 否则不是)
            int pt = 0;
            for (int teword : tewords){
                if ( (teword | (1 << p)) == teword){//满足第一个条件
                    if ( (tepuzzles[i] | teword) == tepuzzles[i]){//或运算   满足第二个条件
//                        res[i]++;
                        pt++;
                    }
                }
            }

            rets.add(pt);
        }
//        System.out.println(Arrays.toString(res));

        return rets;
    }

    /**
     * 不超时版，仅适用于此题
     *
     * @param words
     * @param puzzles
     * @return
     */
    public static List<Integer> findNumOfValidWords2(String[] words, String[] puzzles) {
        Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();//其中的键表示一个长度为 26 的二进制数，值表示其出现的次数

        for (String word : words) {
            int mask = 0;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                mask |= (1 << (ch - 'a'));
            }
            if (Integer.bitCount(mask) <= 7) {//压缩后（不重复）只有七位，才能符合题意
                frequency.put(mask, frequency.getOrDefault(mask, 0) + 1);
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (String puzzle : puzzles) {
            int total = 0;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if ((choose & (1 << i)) != 0) {
            //             mask |= (1 << (puzzle.charAt(i + 1) - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle.charAt(0) - 'a'));
            //     if (frequency.containsKey(mask)) {
            //         total += frequency.get(mask);
            //     }
            // }

            // 枚举子集方法二
            int mask = 0;
            for (int i = 1; i < 7; ++i) {
                mask |= (1 << (puzzle.charAt(i) - 'a'));//得到一个整型数（六位比特位，因为第一位必存在就省略了）
            }
            int subset = mask;
            do {
                int s = subset | (1 << (puzzle.charAt(0) - 'a'));//固定首字母
                if (frequency.containsKey(s)) {
                    total += frequency.get(s);
                }
                subset = (subset - 1) & mask;
            } while (subset != mask);

            ans.add(total);
        }
        return ans;
    }
}
